package a00_LeetCode.Tree;

import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

/**
 * @Author quan
 * @Description ♡♡必须会！！！四大遍历方式必须会！递归方式和非递归方式！
 * 前序遍历的非递归方式
 * @Date 2023/3/28 8:57
 */
public class Num144_PreOrder {
    public List<Integer> preorderTraversal(TreeNode root) {
        /**
         * 前序遍历的非递归方式使用 栈来实现：先将根节点入栈：当栈顶元素出栈的时候，把不断的将该节点的右节点和左节点压入栈
         * 注意顺序不能变：当栈为空，遍历结束
         */

        //定义一个集合
        List<Integer> result = new ArrayList<>();
        //定义一个栈
        Deque<TreeNode> stack = new LinkedList<>();
        //判断树是否为空
        if(root == null){
            return result;
        }
        //让根节点入栈
        stack.push(root);
        //当栈为空的时候，说明遍历结束
        while (!stack.isEmpty()){
            //每次弹出栈顶元素，都将该值添加到集合中，同时让该节点的右节点和左节点入栈
            TreeNode node = stack.pop();
            result.add(node.val);
            if(node.right != null){
                stack.push(node.right);
            }
            if(node.left != null){
                stack.push(node.left);
            }
        }
        //栈为空，则遍历结束
        return result;
    }
}
